package com.hao.sort;

import java.util.*;

/**
 * TODO
 * 基数排序
 * @author 97472
 * @version 1.0
 * @date 2021/5/19 13:25
 */
public class RadixSort {
    public static void main(String[] args) {
        Random random = new Random();
        Integer[] arr = new Integer[10000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }
        long start1 = System.currentTimeMillis();
        radixSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("花费时间："+(end1-start1));
    }
    public static void radixSort(Integer[] arr){
        Queue<Integer>[] radixArrs = new LinkedList[10];
        for (int i = 0; i < radixArrs.length; i++) {
            radixArrs[i] = new LinkedList<>();
        }
        radixSort(arr,radixArrs,1);
    }
    /**
     * 从radixIndex开始基数排序
     * @param arr 需要排序的数组
     * @param radixIndex 基数的位置 1代表个位，2代表十位依次传递下去
     */
    private static void radixSort(Integer[] arr, Queue<Integer>[] radixArrs, Integer radixIndex){
        for (int i = 0; i < arr.length; i++) {
            Integer radix = getRadix(arr[i],radixIndex);
            radixArrs[radix].add(arr[i]);
        }
        if (radixArrs[0].size() != arr.length){
            int j = 0;
            for (int i = 0; i < radixArrs.length; i++) {
                while (!radixArrs[i].isEmpty()){
                    arr[j] = radixArrs[i].poll();
                    j++;
                }
            }
            radixSort(arr,radixArrs,++radixIndex);
        }
    }

    /**
     *  获取一个整数的指定基数
     *  基本原理就是 123 获取10位  123 % 100 =23   23/10 = 2 --->123%100/10 = 2
     * @param num 整数
     * @param radixIndex 指定的基数位置
     */
    private static Integer getRadix(Integer num,Integer radixIndex){
        int radix = 0;
        int temp = (int) Math.pow(10,radixIndex);
        radix = num%temp/(temp/10);
        return radix;
    }
    public static void printlnArr(Integer[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }
}
